The diameter of randomly perturbed digraphs and some applications

The central observation of this paper is that if εn random arcs are added to any n‐node strongly connected digraph with bounded degree then the resulting graph has diameter 𝒪(lnn) with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for digraphs with bounded degree, it is NL‐complete. By XORing an arbitrary bounded degree digraph with a sparse random digraph R ∼ 𝔻_n,ε/n we obtain a “smoothed” instance. We show that, with high probability, a log‐space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if NL ⫅̸ almost‐L then no heuristic can recognize similarly perturbed instances of (s,t)‐connectivity. Property Testing: A digraph is called k‐linked if, for every choice of 2k distinct vertices s₁,…,s_k,t₁,…,t_k, the graph contains k vertex disjoint paths joining s_r to t_r for r = 1,…,k. Recognizing k‐linked digraphs is NP‐complete for k ≥ 2. We describe a polynomial time algorithm for bounded degree digraphs, which accepts k‐linked graphs with high probability, and rejects all graphs that are at least εn arcs away from being k‐linked. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

A scaling limit for the length of the longest cycle in a sparse random digraph

We discuss the length of the longest directed cycle in the sparse random digraph , constant. We show that for large there exists a function such that a.s. The function where is a polynomial in . We are only able to explicitly give the values , although we could in principle compute any .     

Nonvertex‐Balanced Factors in Random Graphs

We prove part of a conjecture by Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1–28.) regarding threshold functions for the existence of an H‐factor in a random graph . We prove that the conjectured threshold function is correct for any graph H which is not covered by its densest subgraphs. We also demonstrate that the main result of Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1–28) generalizes to multigraphs, digraphs, and a multipartite model.     

Complete characterization of almost Moore digraphs of degree three

It is well known that Moore digraphs do not exist except for trivial cases (degree 1 or diameter 1), but there are digraphs of diameter two and arbitrary degree which miss the Moore bound by one. No examples of such digraphs of diameter at least three are known, although several necessary conditions for their existence have been obtained. In this paper, we prove that digraphs of degree three and diameter k ≥ 3 which miss the Moore bound by one do not exist. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 112–126, 2005     

A note on total colourings of digraphs

In the paper two different arc-colourings and two associated with the total colourings of digraphs are considered. In one of these colourings we show that the problem of calculating the total chromatic index reduces to that of calculating the chromatic number of the underlying graph. In the other colouring we find the total chromatic indices of complete symmetric digraphs and tournaments.     

On the longest circuit in an alterable digraph

Analterable digraph is a digraph with a subset of its edges marked alterable and their orientations left undecided. We say that an alterable digraph has an invariant ofk on the length of the longest circuit if it has a circuit of length at leastk regardless of the orientations over its alterable edges. Computing the maximum invariant on the length of the longest circuit in an alterable digraph is aglobal optimization problem. We show that it is hard to approximate the global optimal solution for the maximum invariant problem.Research supported in part by NSF grant CCR 9121472.     

The graph structure of a deterministic automaton chosen at random

An n‐state deterministic finite automaton over a k‐letter alphabet can be seen as a digraph with n vertices which all have k labeled out‐arcs. Grusho (Publ Math Inst Hungarian Acad Sci 5 (1960), 17–61). proved that whp in a random k‐out digraph there is a strongly connected component of linear size, i.e., a giant, and derived a central limit theorem. We show that whp the part outside the giant contains at most a few short cycles and mostly consists of tree‐like structures, and present a new proof of Grusho's theorem. Among other things, we pinpoint the phase transition for strong connectivity. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 428–458, 2017     

Disjoint Paths in Decomposable Digraphs

The k‐linkage problem is as follows: given a digraph and a collection of k terminal pairs such that all these vertices are distinct; decide whether D has a collection of vertex disjoint paths such that is from to for . A digraph is k‐linked if it has a k‐linkage for every choice of 2k distinct vertices and every choice of k pairs as above. The k‐linkage problem is NP‐complete already for [11] and there exists no function such that every ‐strong digraph has a k‐linkage for every choice of 2k distinct vertices of D [17]. Recently, Chudnovsky et al. [9] gave a polynomial algorithm for the k‐linkage problem for any fixed k in (a generalization of) semicomplete multipartite digraphs. In this article, we use their result as well as the classical polynomial algorithm for the case of acyclic digraphs by Fortune et al. [11] to develop polynomial algorithms for the k‐linkage problem in locally semicomplete digraphs and several classes of decomposable digraphs, including quasi‐transitive digraphs and directed cographs. We also prove that the necessary condition of being ‐strong is also sufficient for round‐decomposable digraphs to be k‐linked, obtaining thus a best possible bound that improves a previous one of . Finally we settle a conjecture from [3] by proving that every 5‐strong locally semicomplete digraph is 2‐linked. This bound is also best possible (already for tournaments) [1].     

Strong immersion is a well-quasi-ordering for semicomplete digraphs

We prove that the strong immersion order is a well-quasi-ordering on the class of semicomplete digraphs, thereby strengthening a result of Chudnovsky and Seymour (2011, J. Comb. Theory, Series B, 101, 47–53) that this holds for the class of tournaments.